package com.LeetCode.StackAndHeap;


import org.junit.Test;

import java.util.LinkedList;

/**
 * 移除k位数字使得数字最大小
 */
public class RemoveKNum {

    public String removeKdigits(String num, int k) {
        LinkedList<Character> stack = new LinkedList<>();
        char[] chars = num.toCharArray();
        StringBuilder strb = new StringBuilder();
        for(int i = 0; i<chars.length; i++){
            while(k > 0 && stack.size() > 0 && stack.peekLast() > chars[i]){
                stack.removeLast();
                k--;
            }
            stack.add(chars[i]);
        }

        for(int i=0; i<k; ++i) {
            stack.removeLast();
        }


        boolean leadZero = true;

        for(char c : stack){
            if(c == '0' && leadZero){
                continue;
            }
            leadZero = false;
            strb.append(c);
        }

        return strb.length() == 0 ? "0" : strb.toString();
    }

    @Test
    public void test(){
        System.out.println(removeKdigits("1432219",3));
    }
}
